You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Example 1:
Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete.
Example 2:
Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"
Example 3:
Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps"
Constraints:
1 <= s.length <= 1052 <= k <= 104sonly contains lower case English letters.
Average Rating: 4.66 (44 votes)
Solution
Approach 1: Brute Force
We can do exactly what the problem asks: count repeating adjacent letters and remove them when the count reaches k. Then, we do it again until there is nothing to remove.
Algorithm
-
Remember the length of the string.
-
Iterate through the string:
-
If the current character is the same as the one before, increase the count.
- Otherwise, reset the count to
1.
- Otherwise, reset the count to
-
If the count equals
k, erase lastkcharacters.
-
-
If the length of the string was changed, repeat starting from the first step.
Complexity Analysis
-
Time complexity: O(n2/k), where n is a string length. We scan the string no more than n/k times.
-
Space complexity: O(1). A copy of a string may be created in some languages, however, the algorithm itself only uses the current string.
Approach 2: Memoise Count
If you observe how the count changes in the approach above, you may have an idea to store it for each character. That way, we do not have to start from the beginning each time we remove a substring. This approach will give us linear time complexity, and the trade-off is the extra memory to store counts.
Algorithm
-
Initialize
countsarray of sizen. -
Iterate through the string:
-
If the current character is the same as the one before, set
counts[i]tocounts[i - 1] + 1.- Otherwise, set
counts[i]to1.
- Otherwise, set
-
If
counts[i]equalsk, erase lastkcharacters and decreaseibyk.
-
Complexity Analysis
-
Time complexity: O(n), where n is a string length. We process each character in the string once.
-
Space complexity: O(n) to store the count for each character.
Approach 3: Stack
Instead of storing counts for each character, we can use a stack. When a character does not match the previous one, we push 1 to the stack. Otherwise, we increment the count on the top of the stack.
Algorithm
-
Iterate through the string:
-
If the current character is the same as the one before, increment the count on the top of the stack.
- Otherwise, push
1to the stack.
- Otherwise, push
-
If the count on the top of the stack equals
k, erase lastkcharacters and pop from the stack.
-
Note that, since
Integeris immutable in Java, we need to pop the value first, increment it, and then push it back (if it's less thank).
-
Time complexity: O(n), where n is a string length. We process each character in the string once.
-
Space complexity: O(n) for the stack.
Approach 4: Stack with Reconstruction
If we store both the count and the character in the stack, we do not have to modify the string. Instead, we can reconstruct the result from characters and counts in the stack.
Algorithm
-
Iterate through the string:
-
If the current character is the same as on the top of the stack, increment the count.
- Otherwise, push
1and the current character to the stack.
- Otherwise, push
-
If the count on the top of the stack equals
k, pop from the stack.
-
-
Build the result string using characters and counts in the stack.
Complexity Analysis
- Same as for approach 3 above.
Approach 5: Two Pointers
This method was proposed by @lee215, and we can use it to optimize string operations in approaches 2 and 3. Here, we copy characters within the same string using the fast and slow pointers. Each time we need to erase k characters, we just move the slow pointer k positions back.
Algorithm
-
Initialize the slow pointer (
j) with zero. -
Move the fast pointer (
i) through the string:-
Copy s[i] into s[j].
-
If
s[j]is the same ass[j - 1], increment the count on the top of the stack.- Otherwise, push
1to the stack.
- Otherwise, push
-
If the count equals
k, decreasejbykand pop from the stack.
-
-
Return
jfirst characters of the string.
Complexity Analysis
- Same as for approach 3 above.
November 26, 2019 8:13 PM
Thank you Leetcode for getting me the job at Bloomberg
January 7, 2020 12:53 PM
Using 2 stacks, the solution will become so much intuitive and easy. [Accepted]
- one stack for holding unique elements let's say (stack)
- another stack (let say counter_stack) for storing current count from the stack.peek( )
- Loop through each item in s and adjust/remove top elements of both stacks.
- build a return string using both of the stacks.
- Simple Python3 implementation is below.
def removeDuplicates(s: str, k: int) -> str:
stack = []
counter_stack = []
for val in s:
if not stack or stack[-1]!=val:
stack.append(val)
counter_stack.append(1)
elif stack[-1]==val:
counter_stack[-1]+=1
if counter_stack[-1]==k:
counter_stack.pop()
stack.pop()
return ''.join([stack[i]*counter_stack[i] for i in range(len(stack))])
Last Edit: April 1, 2020 10:59 AM
Just want to point out for some of the solutions, with "sb.delete(i - k + 1, i + 1);", the time complexity won't simply be O(N)..
January 8, 2020 5:26 AM
The two pointers are nice
March 7, 2020 12:49 AM
You can also store an Item{ char c, int count} on the stack and keep popping the stack every time the count is k. At the end, pop the non-empty stack into the result string.
September 22, 2020 8:07 AM
For me, the easiest solution was using 1 stack which holds arrays of the form [c, f] where c is the character and f is the frequency. I've also made a video for anyone looking for a more thorough explanation! :) Happy studying all!
https://www.youtube.com/watch?v=Rq4-1LonjaQ
class Solution:
def removeDuplicates(self, s, k):
#[['c1', n1], ['c2', n2], ...]
stack = []
for c in s:
if stack and stack[-1][0] == c:
stack[-1][1] += 1
if stack[-1][1] >= k:
stack.pop()
else:
stack.append([c, 1])
result = ''
for arr in stack:
result += (arr[0] * arr[1])
return result
July 27, 2020 11:15 AM
I think answers with stacks probably would be more than O(n), since you may have to remove k elements a certain m amount of times. It would be something like O(n + (km)). Any thoughts on that?
Last Edit: June 27, 2020 12:25 AM
The Simplest solution is not mentioned :-)
credit https://leetcode.com/fishercoder/
public String removeDuplicates(String s, int k) {
char last = ' ';
int count = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == last) count++;
else count = 1;
if (count == k)
s = removeDuplicates(s.substring(0, i-k+1) + s.substring(i+1), k);
last = c;
}
return s;
}
October 8, 2020 9:32 AM
is approach 2 considered dynamic programming?
Last Edit: March 30, 2021 3:30 AM
Why can't we use StringBuilder as stack (and sb.setLength to "remove" characters)? When we do "remove" we have to go from the end and count number of "written" characters. But it can happen not more than n/k times and we read no more than k chars, so it's O(N) for time and O(1) for additional space (but O(N) for string that we should return). So, we don't allocate space for stacks/arrays. Do I miss something? I implemented this and reached 98% for time (3ms) and 97.3% for space (38.7MB)
xxxxxxxxxxclass Solution {public: string removeDuplicates(string s, int k) { }};